home *** CD-ROM | disk | FTP | other *** search
/ Aminet 2 / Aminet AMIGA CDROM (1994)(Walnut Creek)[Feb 1994][W.O. 44790-1].iso / Aminet / util / gnu / groff_src.lha / Groff-1.07 / troff / dictionary.cc < prev    next >
C/C++ Source or Header  |  1993-02-23  |  5KB  |  212 lines
  1. // -*- C++ -*-
  2. /* Copyright (C) 1989, 1990, 1991, 1992 Free Software Foundation, Inc.
  3.      Written by James Clark (jjc@jclark.com)
  4.  
  5. This file is part of groff.
  6.  
  7. groff is free software; you can redistribute it and/or modify it under
  8. the terms of the GNU General Public License as published by the Free
  9. Software Foundation; either version 2, or (at your option) any later
  10. version.
  11.  
  12. groff is distributed in the hope that it will be useful, but WITHOUT ANY
  13. WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14. FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15. for more details.
  16.  
  17. You should have received a copy of the GNU General Public License along
  18. with groff; see the file COPYING.  If not, write to the Free Software
  19. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
  20.  
  21.  
  22. #include "troff.h"
  23. #include "symbol.h"
  24. #include "dictionary.h"
  25.   
  26. // is `p' a good size for a hash table
  27.  
  28. static int is_good_size(int p)
  29. {
  30.   const int SMALL = 10;
  31.   for (unsigned i = 2; i <= p/2; i++)
  32.     if (p % i == 0)
  33.       return 0;
  34.   for (i = 0x100; i != 0; i <<= 8)
  35.     if (i % p <= SMALL || i % p > p - SMALL)
  36.       return 0;
  37.   return 1;
  38. }
  39.  
  40. dictionary::dictionary(int n) : threshold(0.5), factor(1.5), used(0), size(n)
  41. {
  42.   table = new association[n];
  43.   for (int i = 0; i < n; i++)
  44.     table[i].v = 0;
  45. }
  46.  
  47. // see Knuth, Sorting and Searching, p518, Algorithm L
  48. // we can't use double-hashing because we want a remove function
  49.  
  50. void *dictionary::lookup(symbol s, void *v)
  51. {
  52.   for (int i = int(s.hash() % size); 
  53.        table[i].v != 0;
  54.        i == 0 ? i = size - 1: --i)
  55.     if (s == table[i].s) {
  56.       if (v != 0) {
  57.     void *temp = table[i].v;
  58.     table[i].v = v;
  59.     return temp;
  60.       }
  61.       else
  62.     return table[i].v;
  63.     }
  64.   if (v == 0)
  65.     return 0;
  66.   ++used;
  67.   table[i].v = v;
  68.   table[i].s = s;
  69.   if ((double)used/(double)size >= threshold || used + 1 >= size) {
  70.     int old_size = size;
  71.     size = int(size*factor);
  72.     while (!is_good_size(size))
  73.       ++size;
  74.     association *old_table = table;
  75.     table = new association[size];
  76.     used = 0;
  77.     for (i = 0; i < old_size; i++)
  78.       if (old_table[i].v != 0)
  79.     (void)lookup(old_table[i].s, old_table[i].v);
  80.     a_delete old_table;
  81.   }
  82.   return 0;
  83. }
  84.  
  85. void *dictionary::lookup(const char *p)
  86. {
  87.   symbol s(p, MUST_ALREADY_EXIST);
  88.   if (s.is_null())
  89.     return 0;
  90.   else
  91.     return lookup(s);
  92. }
  93.  
  94. // see Knuth, Sorting and Searching, p527, Algorithm R
  95.   
  96. void *dictionary::remove(symbol s)
  97. {
  98.   // this relies on the fact that we are using linear probing
  99.   for (int i = int(s.hash() % size);
  100.        table[i].v != 0 && s != table[i].s;
  101.        i == 0 ? i = size - 1: --i)
  102.     ;
  103.   void *p = table[i].v;
  104.   while (table[i].v != 0) {
  105.     table[i].v = 0;
  106.     int j = i;
  107.     int r;
  108.     do {
  109.       --i;
  110.       if (i < 0)
  111.     i = size - 1;
  112.       if (table[i].v == 0)
  113.     break;
  114.       r = int(table[i].s.hash() % size);
  115.     } while ((i <= r && r < j) || (j < i && i <= r));
  116.     table[j] = table[i];
  117.   }
  118.   if (p != 0)
  119.     --used;
  120.   return p;
  121. }
  122.  
  123. dictionary_iterator::dictionary_iterator(dictionary &d) : dict(&d), i(0)
  124. {
  125. }
  126.  
  127. int dictionary_iterator::get(symbol *sp, void **vp)
  128. {
  129.   for (; i < dict->size; i++)
  130.     if (dict->table[i].v) {
  131.       *sp = dict->table[i].s;
  132.       *vp = dict->table[i].v;
  133.       i++;
  134.       return 1;
  135.     }
  136.   return 0;
  137. }
  138.  
  139. object_dictionary_iterator::object_dictionary_iterator(object_dictionary &od)
  140.      : di(od.d)
  141. {
  142. }
  143.  
  144. object::object() : rcount(0)
  145. {
  146. }
  147.  
  148. object::~object()
  149. {
  150. }
  151.  
  152. void object::add_reference()
  153. {
  154.   rcount += 1;
  155. }
  156.  
  157. void object::remove_reference()
  158. {
  159.   if (--rcount == 0)
  160.     delete this;
  161. }
  162.  
  163. object_dictionary::object_dictionary(int n) : d(n)
  164. {
  165. }
  166.  
  167. object *object_dictionary::lookup(symbol nm)
  168. {
  169.   return (object *)d.lookup(nm);
  170. }
  171.  
  172. void object_dictionary::define(symbol nm, object *obj)
  173. {
  174.   obj->add_reference();
  175.   obj = (object *)d.lookup(nm, obj);
  176.   if (obj)
  177.     obj->remove_reference();
  178. }
  179.  
  180. void object_dictionary::rename(symbol oldnm, symbol newnm)
  181. {
  182.   object *obj = (object *)d.remove(oldnm);
  183.   if (obj) {
  184.     obj = (object *)d.lookup(newnm, obj);
  185.     if (obj)
  186.       obj->remove_reference();
  187.   }
  188. }
  189.  
  190. void object_dictionary::remove(symbol nm)
  191. {
  192.   object *obj = (object *)d.remove(nm);
  193.   if (obj)
  194.     obj->remove_reference();
  195. }
  196.  
  197. // Return non-zero if oldnm was defined.
  198.  
  199. int object_dictionary::alias(symbol newnm, symbol oldnm)
  200. {
  201.   object *obj = (object *)d.lookup(oldnm);
  202.   if (obj) {
  203.     obj->add_reference();
  204.     obj = (object *)d.lookup(newnm, obj);
  205.     if (obj)
  206.       obj->remove_reference();
  207.     return 1;
  208.   }
  209.   return 0;
  210. }
  211.  
  212.